Batch 1 - Class 06 - Parity (2)

Pre-class problems:

(Khan Academy: Alien abduction brain teaser) 10 prisoners are given a chance of survival by the jailer. The jailer tells them that the next morning, he will have them stand in a queue (so that the last person can see the nine people in front, the second last people can see eight people in front of him, and so on), and then place either a red hat or a purple hat on each person's head. The person hence will be able to see the color of hat for people in front of him (but not his own hat). The jailer will then start from the last person, and ask each person "What is the color of hat on your head". The person can answer "red" or "purple". If the person's answer is correct, he will be released, else he will be killed. The jailer will then ask the same question to the second last person, and so on. The prisoners have the night to figure out the strategy so that maximum number of prisoners can survive (on a guaranteed basis). Figure out a strategy to save the maximum number of prisoners.

Attendance Muskaan, Smiti, Mahika, Tara, Manas, Arjun, Jasmine, Ishartek

Class puzzles

Homework puzzle
Answer: "Last guy calls the odd number of hats in front". Every person there on keeps a count of odd or even parity. See https://www.khanacademy.org/math/recreational-math/brain-teasers/v/alien-abduction-brain-teaser

Instructor Notes: Take example to explain, let kids do it, try for smaller number to illustrate induction, parity thinking

What is Parity: The state of being even or odd. Can also be used with black or white, clockwise or anticlockwise, and so on. Any two values that are exclusive, and together comprehensive

Can kids identify some things that are always even or odd, or always go from even to odd and odd to even?
Always even - multiply by 2Always odd - multiply by 3Even -> Odd -> Even ... - normal counting
(MC Chap1, Prob 3) Can a knight start at square a1 of the chessboard, and go to h8, visiting each square exactly once?
Answer: No. There are 63 moves in all, and the knight changes color of cell in each move. So if it starts from a white square, it must end up on a black one.

Instructor Note: Let kids discover the black/white parity, and the fact these alternate. Hence 63 moves can not bring it back to same color.

(Contributed by Tara, Mahika) There are 11 pairs of blue socks, 10 pairs of red socks, and 10 pairs of yellow socks in a drawer. The lights are out so you can't see the colors. How many socks do you need to take to be sure that you have got at least two of the same color
Answer: 4. Supplementary problem: How many do you have to take out to ensure that you have at least 2 red socks?
(MC Chap 1, Prob 5) Three hockey pucks A, B, C lie on playing field. A player hits one of them so that it passes between the other two. He does this 25 times. Can he return the pucks to their starting point?
Answer: No. In each move the ABC circle (arbitrarily chosen) goes from clockwise to anti-clockwise or vice-versa. So in odd moves, you cant come back to original position.

Instructor Note: Let kids discover the notion of clockwise and anti-clockewise parity?

Game: - There is a circular table on which two people are playing a game of placing checkers. The person who can place the last checker wins. If you are the first player to go, how will you win?
Answer: Place first move in center, then place every checker symmetrically opposite to what the opponent does. What if it is a hexagonal table?

Instructor Note: Let kids group up and try to play with a smaller board (can use a drawn up circular board with discrete slots for checkers)

(Contributed by Tara, Mahika) There are three boxes, one with two black balls, second with two white balls, and third with a black and a white ball. The labels on the boxes (BB, WW and BW) have got swapped, so that all the labels are wrong. You are allowed to draw balls, one at a time to figure out the correct labels. How many draws are required to get all the labels back to correct boxes.
Answer: 1. Draw from BW box. If it is white ball, then BW box must be relabeled WW, BB box must be relabeled BW, and WW box must be relabeled BB. Similarly for black draw.
(Contributes by Jasmine) My neighbor told me the product of ages of his three daughters is 36. Then he told me the sum of their ages was same as his house number, but I still couldn't tell their ages. Then he told me his eldest daughter plays the piano. What are the ages of his daughters?
Answer: 2, 2, 9. Amongst all possibilities that multiply to 36, only 9,2,2 and 6,6,1 have same sum (and hence I am unable to tell by the sum). Since there is an eldest daughter, it must be 9,2,2.
(MartinShCol - 1.16) In the class, you are allowed to shake hands with each other as many number of times as you want. At every stage, people who have shaken hands odd number of times remain standing. Tell your observation.
Answer: Number of people standing is always even. Why?
(MartinShCol - 1.6) Take a 3x3 Rubik cube. A termite starts at one of the outer cubes, and goes from one cube to next, never coming back to a cube it has been through, and never going diagonal. Is it possible for the termite to bore through each of 26 outer cubes and finish the trip at the center cube?
Answer: No. Color alternate cubes black and white. Termite alternates between colors on the cube, and hence can not finish at the center square, which is in the 13 color set (not in the 14 color set)

Instructor Note: Tougher problem. Let students work on it. Then give them a hint to think of this as a two color cube with alternate colors.

(MC Chap 1, Prob 20) Numbers 1 to 10 are written in a row. Can you insert signs + and - so that the value of resulting expression is 0?
Answer: No. Sum is 55, and changing any sign changes the result by even number

Homework puzzles

(MC Chap 1, Prob 31) Of 101 coins, 50 are counterfeit and differ from genuine coins by 1gm (positive or negative). There is a balance which shows difference in weight on two pans. You choose 1 coin and want to determine in one weighing if it is genuine or counterfeit
Answer: Weight remaining 50 against 50. Regardless of the mix, if the difference is even, then the coin outside is genuine, else fake

Instructor Notes: Try working with smaller numbers. If they are not able to get it, try working with simpler case that all fake are positive 1gm.

(Khan Academy: light bulb) - 100 bulbs, 100 passes, initially all off. On each nth pass toggle all bulbs which are multiple of n. After 100 passes, how many and which bulbs are on
Answer: all squares - i.e. 1, 4, 9, 16, 25, 36, ..100 (10 bulbs)

Instructor Notes: helps to solve for smaller numbers first, and let kids see the pattern

Additional puzzles

(MartinShCol - 12.1) Your king is on a corner cell of a chessboard, and opponent's knight is on the corner cell diagonally opposite. Knight moves first. For how many moves can the king avoid being checked?
Answer: Forever. Move the king towards center and always keep it in opposite color to knight, so that when knight moves it will not be able to check, since knight always changes color on a move. Why is it important to be in center?

Instructor Note: Remind of prior knight problem, and the fact that knight always changes color on the move

(MC Chap1, Prob 16) Can one make change for a 25-rupee note, using in all ten bills each of 1,3, or 5 rupees?
Answer: No. Sum of even number of odd numbers is even

References:

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg

The Colossal Book of Short Puzzles and Problems, by Martin Gardner

Khan Academy - https://www.khanacademy.org/math/recreational-math/brain-teasers/v/alien-abduction-brain-teaser